package myGraph;


import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

class ArcNode            //边结点类
{
    int adjvex;            //该边的终点编号
    ArcNode nextarc;        //指向下一条边的指针
    int weight;            //该边的相关信息,如边的权值
}

class VNode            //头结点类
{
    String[] data;        //顶点信息
    ArcNode firstarc;        //指向第一条边的邻接顶点
}

public class AdjGraph  //图邻接表类
{
    final int MAXV = 100;        //表示最多顶点个数
    final int INF = 0x3f3f3f3f;    //表示∞
    VNode[] adjlist;        //邻接表头数组
    static int[] visited;
    int n, e;            //图中顶点数n和边数e

    public AdjGraph()    //构造方法
    {
        adjlist = new VNode[MAXV];
        for (int i = 0; i < MAXV; i++)
            adjlist[i] = new VNode();
    }

    //图的基本运算算法
    public void createAdjGraph(int[][] a, int n, int e) {
        this.n = n;
        this.e = e;            //置顶点数和边数
        ArcNode p;
        for (int i = 0; i < n; i++)            //所有头结点的指针置初值
            adjlist[i].firstarc = null;
        for (int i = 0; i < n; i++)            //检查边数组a中每个元素
            for (int j = n - 1; j >= 0; j--)
                if (a[i][j] != 0 && a[i][j] != INF)    //存在一条边
                {
                    p = new ArcNode();            //创建一个边结点p
                    p.adjvex = j;
                    p.weight = a[i][j];
                    p.nextarc = adjlist[i].firstarc;  //采用头插法插入p
                    adjlist[i].firstarc = p;
                }
    }

    public void dispAdjGraph()        //输出图的邻接表
    {
        ArcNode p;
        for (int i = 0; i < n; i++) {
            System.out.printf("  [%d]", i);
            p = adjlist[i].firstarc;        //p指向第一个邻接点
            while (p != null) {
                System.out.printf("->(%d,%d)", p.adjvex, p.weight);
                p = p.nextarc;            //p移向下一个邻接点
            }
            System.out.println("->∧");
        }
    }

    public static void DFS(AdjGraph G, int v) { //邻接表深度遍历
        int w;
        ArcNode p;
        System.out.print(v + " ");        //访问顶点v
        visited[v] = 1;            //置已访问标记
        p = G.adjlist[v].firstarc;        //p指向顶点v的第一个邻接点
        while (p != null) {
            w = p.adjvex;
            if (visited[w] == 0) DFS(G, w);            //若w顶点未访问,递归访问它
            p = p.nextarc;            //p置为下一个邻接点
        }
    }

    public static void BFS(AdjGraph G, int v) {//邻接表广度遍历
        ArcNode p;
        int w;
        Queue<Integer> qu = new LinkedList<Integer>();    //定义一个队列
        System.out.print(v + " ");            //访问顶点v
        visited[v] = 1;                //置已访问标记
        qu.offer(v);                //v进队
        while (!qu.isEmpty())            //队列不空循环
        {
            v = qu.poll();                //出队顶点v
            p = G.adjlist[v].firstarc;        //找顶点v的第一个邻接点
            while (p != null) {
                w = p.adjvex;
                if (visited[w] == 0)            //若v的邻接点w未访问
                {
                    System.out.print(w + " ");        //访问顶点w
                    visited[w] = 1;            //置已访问标记
                    qu.offer(w);            //w进队
                }
                p = p.nextarc;                //找下一个邻接顶点
            }
        }
    }

    public static void DFSA(AdjGraph G)    //非连通图的DFS
    {
        Arrays.fill(visited, 0);        //visited数组元素均置为0
        for (int i = 0; i < G.n; i++)
            if (visited[i] == 0) DFS(G, i);            //从顶点i出发深度优先遍历
    }

    public static void BFSA(AdjGraph G)    //非连通图的BFS
    {
        Arrays.fill(visited, 0);        //visited数组元素均置为0
        for (int i = 0; i < G.n; i++)
            if (visited[i] == 0) BFS(G, i);            //从顶点i出发广度优先遍历
    }

}


